문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 유클리드 호제법 (문단 편집) == 증명 == [math(\gcd\left(a,\ b\right)=G)], [math(\gcd\left(b,\ r\right)=G')]이라 하자. 적당한 [[서로소]]인 [[정수]] [math(A,B)]에 대해 [math(a=GA,b=GB)]가 성립한다. 이를 [math(a=bq+r)]에 대입하면, [math(GA=GBq+r)]이고, [math(r=G\left(A-Bq\right))]이다. 여기서 [math(G)]는 [math(b)]와 [math(r)]의 공약수임을 알 수 있다. 즉, [math(G)]는 [math(G')]의 약수이다. [math(G'=mG)]로 두자. 그러면 적당한 서로소인 두 [[정수]] [math(k,l)]에 대해 [math(GB=G'k=Gmk, G(A-Bq)=G'l=Gml)]이 성립한다. 양변을 [math(G)]로 나누면 [math(B=mk, A-Bq=ml)]이다. [math(A=ml+Bq=ml+mkq=m\left(l+kq\right))]에서 [math(m)]은 [math(A)]와 [math(B)]의 공약수인데, [math(gcd(A,B)=1)]이므로 항상 [math(m=1)]이고 [math(G'=G)]이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기